package com.lx.algorithm.code.xly3.class03;

import static com.lx.algorithm.Utils.printMatrix;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2022-01-05 00:54:04
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2022-01-05     张李鑫                     1.0         1.0 Version
 */
public class Code05 {
    /**
     * 请注意区分子串和子序列的不同，
     * 给定两个字符串str1和str2，求两个字符串的最长公共子串
     * <p>
     * 动态规划的空间压缩技巧！
     */

//    public static int lcSubString(String str1, String str2) {
//        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
//            return 0;
//        }
//        return process(str1.toCharArray(), str2.toCharArray(), str1.length() - 1, str2.length() - 1);
//    }
    public static int dp(String str1, String str2) {
        if (str1 == null || str1.length() == 0 || str2 == null || str2.length() == 0) {
            return 0;
        }
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();

        int[][] dp = new int[s1.length + 1][s2.length + 1];

        for (int i = dp.length - 2; i >= 0; i--) {
            for (int j = dp[i].length - 2; j >= 0; j--) {
                dp[i][j] = s1[i] == s2[j] ? dp[i + 1][j + 1] + 1 : Math.max(dp[i + 1][j], dp[i][j + 1]);
            }
        }
        return dp[0][0];
    }

    public static int dpII(String s1, String s2) {
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();

        int[][] dp = new int[str1.length][str2.length];
        for (int i = 0; i < str1.length; i++) {
            if (str1[i] == str2[0]) {
                dp[i][0] = 1;
            }
        }
        for (int j = 1; j < str2.length; j++) {
            if (str1[0] == str2[j]) {
                dp[0][j] = 1;
            }
        }
        int max = 0;
        for (int i = 1; i < str1.length; i++) {
            for (int j = 1; j < str2.length; j++) {
                if (str1[i] == str2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    max = Math.max(dp[i][j], max);
                }
            }
        }
        //如果需要返回字符串 就直接substring max i的索引记录一下就好了
        return max;
    }


    public static void main(String[] args) {
        String str1 = "ab1232323c";
        String str2 = "ab23232323c";
//        System.out.println(lcSubString(str1, str2));
        System.out.println(dpII(str1, str2));
    }
}